package com.ctwom.algorithm.questions.Blinkedlist;

/**
 * 删除链表中倒数第N个节点
 */
public class DelDaoshuNNode {
    public static void main(String[] args) {
        Node node4 = new Node(4, null);
        Node node3 = new Node(3, node4);
        Node node2 = new Node(2, node3);
        Node node1 = new Node(1, node2);
        Node node = delDaoshuNNode2(node1, 4);
        Node.forEachNodes(node);
    }

    /**
     * 这个记不住，百度的思路：两个指针，第一个指针先走N步，然后两个指针同时开始遍历链表，直到第一个指针到达表尾
     * 然后第二个指针就可以定位到倒数第N个节点了，然后让倒数第N的前一个节点的next指向倒数第N个节点的next节点，就ok了
     * @param head
     * @param n
     * @return
     */
    public static Node delDaoshuNNode2(Node head, int n){
        if(head == null){
            throw new RuntimeException("链表为空");
        }
        Node first = head;
        Node second = head;
        Node secondPre = second;
        for(int i=1;i<n;i++){
            first = first.next;
            if(first == null){
                throw new RuntimeException("N大于链表长度");
            }
        }
        if(first.next == null){
            //del head
            Node newHead = head.next;
            head.next = null;
            return newHead;
        }
        while(first.next != null){
            first = first.next;
            secondPre = second;
            second = second.next;
        }
        secondPre.next = second.next;
        return head;
    }

}
